package com.ywk.base.javaBase.collection.map;

import com.ywk.base.javaBase.collection.list.LRUCache;
import org.apache.el.util.ConcurrentCache;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.WeakHashMap;
import java.util.concurrent.ConcurrentHashMap;

/**
 * - TreeMap：基于红黑树实现。
 * - HashMap：基于哈希表实现 （数组+链表/红黑树）。
 * - HashTable：和 HashMap 类似，但它是线程安全的，这意味着同一时刻多个线程同时写入 HashTable 不会导致数据不一致。它是遗留类，不应该去使用它，而是使用 ConcurrentHashMap 来支持线程安全，ConcurrentHashMap 的效率会更高，因为 ConcurrentHashMap 引入了分段锁。
 * - LinkedHashMap：使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用（LRU）顺序。
 *
 * @Author zbh
 * @Date 2023/3/30
 */
public class MapDemo {

    public static void main(String[] args) {
        /*===================================HashMap======================================*/
        /**
         * 使用 Entry 类型的数组 table 存储信息，Entry 存储着键值对，从 next 字段可以看出 Entry 是一个链表，即数组中的每个位置被当成一个桶，
         * 一个桶存放一个链表。HashMap 使用拉链法来解决冲突，同一个链表中存放哈希值和散列桶取模运算结果相同的 Entry，链表查找时间复杂度为O(N)。当链表
         * 元素大于等于8时（原码属性：TREEIFY_THRESHOLD），链表将变成红黑树，时间复杂度降低为O(logN)，当红黑树的节点小于或等于 6 个以后，又会恢复为链表形态
         *
         * 拉链法原理：
         * 插入：
         * HashMap默认大小 16k
         * - 插入 <K1,V1> 键值对，先计算 K1 的 hashCode 为 115，使用除留余数法得到所在的桶下标 115%16=3。
         * - 插入 <K2,V2> 键值对，先计算 K2 的 hashCode 为 118，使用除留余数法得到所在的桶下标 118%16=6。
         * - 插入 <K3,V3> 键值对，先计算 K3 的 hashCode 为 118，使用除留余数法得到所在的桶下标 118%16=6，插在 <K2,V2> 后面。
         *
         * 查找（分两步）：
         * - 计算键值对所在的桶；
         * - 在链表上顺序查找，时间复杂度显然和链表的长度成正比。
         *
         * 扩容机制：数组元素 > 初始容量大小（16） * 加载因子（0.75f），调用 rehash()方法进行扩容
         * （注：
         * jdk1.7中采用表头插入法，在扩容时会改变链表中元素原本的顺序，以至于在并发场景下导致链表成环的问题
         * jdk1.8中采用的是尾部插入法，在扩容时会保持链表元素原本的顺序，巧妙地采用和扩容后容量进行&操作来计算新的索引位置，就不会出现链表成环的问题了）
         *
         * */
        HashMap<String, Object> hashMap = new HashMap<>();
        hashMap.put("K1", "V1");
        hashMap.put("K2", "V2");
        hashMap.put("K3", "V3");

        /*===================================ConcurrentHashMap======================================*/
        /**
         * JDK 1.7 使用分段锁机制来实现并发更新操作，核心类为 Segment，它继承自重入锁 ReentrantLock，并发度与 Segment 数量相等。
         * JDK 1.8 使用了 CAS 操作来支持更高的并发度，在 CAS 操作失败时使用内置锁 synchronized。
         * 并且 JDK 1.8 的实现也在链表过长时会转换为红黑树
         */
        ConcurrentHashMap<String, Object> concurrentHashMap = new ConcurrentHashMap<>();

        /*===================================LinkedHashMap======================================*/

        /**
         * 继承自 HashMap，内部维护了一个双向链表，用来维护插入顺序或者 LRU 顺序
         *
         * 适用场景：LRU（最近最少使用，在链表容量有限的情况下保证缓存中的数据都是热点数据） 缓存
         *
         * 维护顺序最重要的两个的函数：访问节点函数 afterNodeAccess(),节点插入后函数 afterNodeInsertion()
         * 当一个节点被访问时（增改查，即调用afterNodeAccess()方法），如果 accessOrder（默认为 false） 为 true，则会将该节点移到链表尾部。
         * 也就是说指定为 LRU 顺序之后，在每次访问一个节点时，会将这个节点移到链表尾部，保证链表尾部是最近访问的节点，那么链表首部就是最近最久未使用的节点。
         * afterNodeInsertion()在 put 等操作之后执行，当 removeEldestEntry()（默认返回 false） 方法返回 true 时会移除最晚的节点，也就是链表首部节点 first。
         *
         */
        LinkedHashMap<String, Object> linkedHashMap = new LinkedHashMap<>();
        //自定义实现 LRU缓存
        LRUCache<Integer, String> lruCache = new LRUCache<>();
        lruCache.put(1, "a");
        lruCache.put(2, "b");
        lruCache.put(3, "c");
        lruCache.get(1);
        lruCache.put(4, "d");
        System.out.println(lruCache.keySet());

        /*===================================WeakHashMap======================================*/
        /**
         *
         * WeakHashMap 的 Entry 继承自 WeakReference(弱引用)，被 WeakReference 关联的对象在下一次垃圾回收时会被回收。
         *
         * ConcurrentCache 使用了 WeakHashMap 来实现缓存功能
         * ConcurrentCache 采取的是分代缓存：
         * - 经常使用的对象放入 eden 中，eden 使用 ConcurrentHashMap 实现，不用担心会被回收；
         * - 不常用的对象放入 longterm，longterm 使用 WeakHashMap 实现，这些老对象会被垃圾收集器回收。
         * - 当调用  get() 方法时，会先从 eden 区获取，如果没有找到的话再到 longterm 获取，当从 longterm 获取到就把对象放入 eden 中，从而保证经常被访问的节点不容易被回收。
         * - 当调用 put() 方法时，如果 eden 的大小超过了 size，那么就将 eden 中的所有对象都放入 longterm 中，利用虚拟机回收掉一部分不经常使用的对象。
         */
        WeakHashMap<Object, Object> weakHashMap = new WeakHashMap<>();
        ConcurrentCache<String, Object> concurrentCache = new ConcurrentCache<String, Object>(10);



    }
}
